﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Data;
using System.Windows.Documents;
using System.Windows.Input;
using System.Windows.Media;
using System.Windows.Media.Imaging;
using System.Windows.Navigation;
using System.Windows.Shapes;

namespace tubao {


/// <summary>
/// MainWindow.xaml 的交互逻辑
/// </summary>
public partial class MainWindow : Window {
	/// <summary>
	/// 工具函数，生成随机种子
	/// </summary>
	/// <returns>返回随机整形变量</returns>
	public int GetRandomSeed ( ) {
		byte[] bytes = new byte[4];
		System.Security.Cryptography.RNGCryptoServiceProvider rng = new System.Security.Cryptography.RNGCryptoServiceProvider ( );
		rng.GetBytes ( bytes );
		return BitConverter.ToInt32 ( bytes, 0 );
	}
	/// <summary>
	/// 鼠标滚轮事件监听改变生成点的数量
	/// </summary>
	/// <param name="sender"></param>
	/// <param name="e"></param>
	private void PointsSlider_MouseWheel ( object sender, MouseWheelEventArgs e ) {
		if (e.Delta > 0)
			PointsSlider.Value++;
		else
			PointsSlider.Value--;
	}
	private void AmountOfPoints_MouseWheel ( object sender, MouseWheelEventArgs e ) {
		if (e.Delta > 0)
			PointsSlider.Value++;
		else
			PointsSlider.Value--;
	}
	private void RandPoints_MouseWheel ( object sender, MouseWheelEventArgs e ) {
		if (e.Delta > 0)
			PointsSlider.Value++;
		else
			PointsSlider.Value--;
	}

	public MainWindow ( ) {
		InitializeComponent ( );
		this.Loaded += new RoutedEventHandler ( this.initCanvas );
	}

	Rectangle[,] RMartix;
	int[,] Martix;
	List<Point> Points;
	private void resizeCanvas ( ) {
		for (int i = 0; i < 100; i++) {
			for (int j = 0; j < 100; j++) {
				Rectangle r = RMartix[i, j];
				r.Width = Canvas.ActualWidth / 100;
				r.Height = Canvas.ActualHeight / 100;
				r.SetValue ( Canvas.TopProperty, i * r.Height );
				r.SetValue ( Canvas.LeftProperty, j * r.Width );
			}
		}
	}
	private void initCanvas ( object sender, RoutedEventArgs e ) {
		RMartix = new Rectangle[100, 100];
		for (int i = 0; i < 100; i++) {
			for (int j = 0; j < 100; j++) {
				Rectangle r = new Rectangle ( );
				r.Width = Canvas.ActualWidth / 100;
				r.Height = Canvas.ActualHeight / 100;
				r.SetValue ( Canvas.TopProperty, i * r.Height );
				r.SetValue ( Canvas.LeftProperty, j * r.Width );
				Canvas.Children.Add ( r );
				RMartix[i, j] = r;
				r.Fill = new SolidColorBrush ( Colors.White );
			}
		}
	}
	private void initData ( ) {
		Points = new List<Point> ( );
		Martix = new int[100, 100];
		for (int i = 0; i < 100; i++) {
			for (int j = 0; j < 100; j++) {
				if (Martix[i, j] != -1) {
					Martix[i, j] = -1;
					RMartix[i, j].Fill = new SolidColorBrush ( Colors.White );
				}
			}
		}
	}

	private void RandPoints_Click ( object sender, RoutedEventArgs e ) {

		new Thread ( ( ) => {
			Dispatcher.BeginInvoke ( new Action ( ( ) => {
				initData ( );
				//清理直线
				if (finalLines != null)
					foreach (Line l in finalLines)
						Canvas.Children.Remove ( l );
				int n = int.Parse ( AmountOfPoints.Content.ToString ( ) );
				for (int i = 0; i < n; i++) {
					int x = new Random ( GetRandomSeed ( ) ).Next ( 0, 100 );
					int y = new Random ( GetRandomSeed ( ) ).Next ( 0, 100 );
					if (Martix[x, y] == -1) {
						Martix[x, y] = 1;
						Points.Add ( new Point ( x, y ) );
						RMartix[x, y].Fill = new SolidColorBrush ( Colors.Red );
					} else {
						i--;
					}
				}
			} ) );
		} ).Start ( );
	}

	Thread t;
	List<Point> finalPoints;
	List<Line> finalLines;
	private void GiftWrapingALG ( ) {
		t = new Thread ( ( ) => {

			//清理直线
			if (finalLines != null)
				foreach (Line l in finalLines)
					Dispatcher.Invoke ( new Action ( ( ) => {
					Canvas.Children.Remove ( l );
				} ) );



			finalPoints = new List<Point> ( );
			finalLines = new List<Line> ( );
			Point firstP = Points.ElementAt ( 0 );
			foreach (Point p in Points) {
				if (p.Y < firstP.Y) {
					firstP = p;
				} else if (p.Y == firstP.Y) {
					if (p.X > firstP.X)
						firstP = p;
				}
			}
			Dispatcher.Invoke ( new Action ( ( ) => {
				RMartix[(int)firstP.X, (int)firstP.Y].Fill = new SolidColorBrush ( Colors.Green );
			} ) );

			do {
				Thread.Sleep ( 100 );
				Point finalLastP;
				//获取当前基准点
				if (finalPoints.Count ( ) == 0)
					finalLastP = firstP;
				else
					finalLastP = finalPoints.ElementAt ( finalPoints.Count ( ) - 1 );

				Point bestP = Points.Except ( finalPoints ).ElementAt ( 0 );

				Dispatcher.Invoke ( new Action ( ( ) => {
					Line l = getDrawLine ( finalLastP, bestP );
					Canvas.Children.Add ( l );
					finalLines.Add ( l );
				} ) );

				foreach (Point P in Points.Except ( finalPoints )) {

					if (getChaCheng ( finalLastP, P, bestP ) > 0) {
						Thread.Sleep ( 100 );
						bestP = P;

						Dispatcher.Invoke ( new Action ( ( ) => {
							Canvas.Children.Remove ( finalLines.ElementAt ( finalLines.Count ( ) - 1 ) );
							finalLines.RemoveAt ( finalLines.Count ( ) - 1 );
							finalLines.Add ( getDrawLine ( finalLastP, bestP ) );
							Canvas.Children.Add ( finalLines.Last ( ) );
						} ) );
					} else if (getChaCheng ( finalLastP, P, bestP ) == 0) {
						if (finalLastP != firstP && distance ( finalLastP, P ) < distance ( finalLastP, bestP )) {
							Thread.Sleep ( 100 );
							bestP = P;
							Dispatcher.Invoke ( new Action ( ( ) => {
								Canvas.Children.Remove ( finalLines.ElementAt ( finalLines.Count ( ) - 1 ) );
								finalLines.RemoveAt ( finalLines.Count ( ) - 1 );
								finalLines.Add ( getDrawLine ( finalLastP, bestP ) );
								Canvas.Children.Add ( finalLines.Last ( ) );
							} ) );
						}

					}
				}
				finalPoints.Add ( bestP );
				Dispatcher.Invoke ( new Action ( ( ) => {
					RMartix[(int)bestP.X, (int)bestP.Y].Fill = new SolidColorBrush ( Colors.Green );
				} ) );


				Dispatcher.Invoke ( new Action ( ( ) => {

					Line l1 = getDrawLine ( finalLastP, finalLastP );
					Canvas.Children.Add ( l1 );
					finalLines.Add ( l1 );
				} ) );



			} while (finalPoints.Count ( ) != 0 && !finalPoints.ElementAt ( finalPoints.Count ( ) - 1 ).Equals ( firstP ));

		} );
		t.SetApartmentState ( ApartmentState.STA );

		t.Start ( );
	}

	/// <summary>
	///格林汉姆算法
	/// </summary>
	///TODO:未实现
	private void GrahamALG ( ) {
		Thread t = new Thread ( ( ) => {
			if (finalLines != null)
				foreach (Line l in finalLines)
					Dispatcher.Invoke ( new Action ( ( ) => {
					Canvas.Children.Remove ( l );
				} ) );
			Stack<Point> finalPointsStack;
			finalPointsStack = new Stack<Point> ( );
			finalLines = new List<Line> ( );
			Point firstP = Points.ElementAt ( 0 );
			foreach (Point p in Points) {
				if (p.Y < firstP.Y) {
					firstP = p;
				} else if (p.Y == firstP.Y) {
					if (p.X > firstP.X)
						firstP = p;
				}
			}

			Stack<Point> sortPoints = new Stack<Point> ( );
			sortPoints.Push ( firstP );

			while (Points.Except ( sortPoints ).Count ( ) > 0) {
				Console.WriteLine ( Points.Except ( sortPoints ).Count ( ) );
				Point bestP = Points.Except ( sortPoints ).ElementAt ( 0 );
				foreach (Point p in Points.Except ( sortPoints )) {
					if (getChaCheng ( firstP, p, bestP ) > 0) {
						bestP = p;
					} else if (getChaCheng ( firstP, p, bestP ) == 0) {
						if (distance ( firstP, p ) < distance ( firstP, bestP )) {
							bestP = p;
						}
					}
				}
				sortPoints.Push ( bestP );
			}
			sortPoints.Reverse ( );
			finalPointsStack.Push ( sortPoints.Pop ( ) );
			finalPointsStack.Push ( sortPoints.Pop ( ) );
			while (sortPoints.Count ( ) != 0) {

			}

		} );
		t.SetApartmentState ( ApartmentState.STA );
		t.Start ( );
	}

	List<Line> beClearLines = new List<Line> ( );
	/// <summary>
	/// 快包算法
	/// </summary>
	private void QuickHallALG ( ) {
		t = new Thread ( ( ) => {
			if (finalLines != null)
				foreach (Line l in finalLines)
					Dispatcher.Invoke ( new Action ( ( ) => {
					Canvas.Children.Remove ( l );
				} ) );
			finalPoints = new List<Point> ( );
			finalLines = new List<Line> ( );
			Point leftP = Points.ElementAt ( 0 );
			Point rightP = leftP;
			foreach (Point p in Points) {
				if (p.Y < leftP.Y) {
					leftP = p;
				} else if (p.Y == leftP.Y) {
					if (p.X < leftP.X)
						leftP = p;
				}

				if (p.Y > rightP.Y) {
					rightP = p;
				} else if (p.Y == rightP.Y) {
					if (p.X > rightP.X)
						rightP = p;
				}
			}
			finalPoints.Add ( leftP );
			finalPoints.Add ( rightP );
			List<Point> topPoints = new List<Point> ( );
			List<Point> bottomPoints = new List<Point> ( );
			Dispatcher.Invoke ( new Action ( ( ) => {
				RMartix[(int)leftP.X, (int)leftP.Y].Fill = new SolidColorBrush ( Colors.Green );
				RMartix[(int)rightP.X, (int)rightP.Y].Fill = new SolidColorBrush ( Colors.Green );
			} ) );
			//构造上包全部点和下包全部点
			foreach (Point p in Points) {
				if (getChaCheng ( leftP, p, rightP ) > 0) {
					bottomPoints.Add ( p );
				};
				if (getChaCheng ( leftP, p, rightP ) < 0) {
					topPoints.Add ( p );
				}
			}
			Thread.Sleep ( 100 );
			Dispatcher.Invoke ( new Action ( ( ) => {
				Line l1 = getDrawLine ( leftP, rightP );
				l1.Stroke = System.Windows.Media.Brushes.DarkGreen;
				beClearLines.Add ( l1 );
				Canvas.Children.Add ( l1 );
			} ) );

			//递归
			QuickHallRecursion ( rightP, leftP, topPoints );
			QuickHallRecursion ( leftP, rightP, bottomPoints );
			foreach (Line L in beClearLines) {
				Dispatcher.Invoke ( new Action ( ( ) => {
					Canvas.Children.Remove ( L);
				} ) );

			}
			beClearLines.Clear ( );
		} );
		t.SetApartmentState ( ApartmentState.STA );
		t.Start ( );




	}
	private void QuickHallRecursion ( Point leftP, Point rightP, List<Point> Sets ) {
		if (Sets.Count ( ) != 0) {
			Point bestP = Sets.ElementAt(0);
			foreach (Point p in Sets) {
				if (getArea ( leftP, rightP, p ) > getArea ( leftP, rightP, bestP )) {
					bestP = p;
				}
			}
			List<Point> leftPoints = new List<Point> ( );
			List<Point> rightPoints = new List<Point> ( );
			foreach (Point p in Sets) {
				if (getChaCheng ( leftP, p,bestP  ) > 0) {
					leftPoints.Add ( p );
				};
				if(getChaCheng ( bestP, p, rightP ) > 0) {
					rightPoints.Add ( p );
				}
			}

			Dispatcher.Invoke ( new Action ( ( ) => {
				Line l2 = getDrawLine ( leftP, bestP );
				l2.Stroke = System.Windows.Media.Brushes.DarkGreen;
				beClearLines.Add ( l2 );
				Canvas.Children.Add ( l2 );
			} ) );


			QuickHallRecursion ( leftP, bestP, leftPoints );

			Dispatcher.Invoke ( new Action ( ( ) => {
				Line	l2 = getDrawLine ( rightP, bestP );
				l2.Stroke = System.Windows.Media.Brushes.DarkGreen;
				beClearLines.Add ( l2);
				Canvas.Children.Add ( l2 );
			} ) );

			QuickHallRecursion ( bestP, rightP, rightPoints );
		} else {
			Thread.Sleep ( 100);
			Dispatcher.Invoke ( new Action ( ( ) => {
				RMartix[(int)leftP.X, (int)leftP.Y].Fill = new SolidColorBrush ( Colors.Green );
				RMartix[(int)rightP.X, (int)rightP.Y].Fill = new SolidColorBrush ( Colors.Green );
				Line l=	getDrawLine ( leftP, rightP );
				Canvas.Children.Add ( l );
				finalLines.Add ( l );
			} ) );
		}

	}
	private double getArea(Point p1,Point p2,Point p3 ) {
		return	Math.Abs ( p1.X * p2.Y + p3.X * p1.Y + p2.X * p3.Y - p3.X * p2.Y - p2.X * p1.Y - p1.X * p3.Y ) / 2;
	}
	private double getChaCheng (Point finalLastP, Point p, Point bestP ) {
		return (p.X - finalLastP.X) * (bestP.Y - finalLastP.Y) - (bestP.X - finalLastP.X) * (p.Y - finalLastP.Y);
	}
	private double distance( Point p1, Point p2 ) {
		return	(p1.X - p2.X) * (p1.X - p2.X) + (p1.Y - p2.Y) * (p1.Y - p2.Y);
	}
	private Line getDrawLine(Point p1  ,Point p2 ) {

		Line l= new Line ( );

		l.Stroke = System.Windows.Media.Brushes.Blue;

		l.Y1 = RMartix[0, 0].ActualHeight / 2 + p1.X * RMartix[0, 0].ActualHeight;
		l.X1 = RMartix[0, 0].ActualWidth / 2 + p1.Y * RMartix[0, 0].ActualWidth;
		l.Y2 = RMartix[0, 0].ActualHeight / 2 + p2.X * RMartix[0, 0].ActualHeight;
		l.X2 = RMartix[0, 0].ActualWidth / 2 + p2.Y * RMartix[0, 0].ActualWidth;

		l.StrokeThickness = 3;
		l.HorizontalAlignment = HorizontalAlignment.Left;
		l.VerticalAlignment = VerticalAlignment.Center;

		return l;
	}
	private void StartDisplay_Click ( object sender, RoutedEventArgs e ) {
		if (t != null) {
			t.Abort ( );
		}
		if (Points != null) {
			switch (ComboxSelectALG.SelectedIndex) {
			case 0:
				GiftWrapingALG ( );

				break;
			case 1:
				GiftWrapingALG ( );
				break;
			case 2:
				QuickHallALG ( );
				break;
			}
		}
	}

	private void Window_SizeChanged ( object sender, SizeChangedEventArgs e ) {
		if (RMartix != null) {
			resizeCanvas ( );
		}
	}

	private void ComboxSelectALG_SelectionChanged ( object sender, SelectionChangedEventArgs e ) {

	}

	private void ComboxSelectALG_LayoutUpdated ( object sender, EventArgs e ) {


		switch (ComboxSelectALG.SelectedIndex) {
		case 0:
			information.Text = "卷包裹法是基于蛮力法改进的,一种快速在随机点中寻找凸包的方法。\n运用极角和向量判断点的位置。\n其平均时间复杂度为O(mn)，但最坏时间复杂度为O(n^2)。\n在随机点中的表现比Graham扫描法要更为优秀。";
			break;
		case 1:
			information.Text = "Graham扫描法本质上和卷包裹法相同，但利用极角和向量对点的位置进行预排序再处理后，其时间复杂度降为O(nlogn)。在点很密集的时候表现极为优秀。";
			break;
		case 2:
			information.Text = "快包算法结合上述两种算法的优点与一身，无论在点密集还是随机分布时都有很好的性能。\n在点集均匀分布时 快速凸包的复杂度更是达到了O(n) 。其性能是上面两种算法难以企及的，绝大多数情况下平均时间复杂度降为O(nlogn)也是非常高效的。\n实现过程继承了快速排序分治思想，运用了递归的过程。";
			break;
		}

	}
}
}

